package com.datastructure.test.verifysquenceofbstcore;

public class VerifySquenceOfBSTCore {

    public static void main(String[] args) {

    }

    public boolean VerifySquenceOfBSTCore(int[] sequence,int start,int end){
        if(start >= end){
            return true;
        }
        int i = start;
        //后续遍历为左右根
        //该二叉树的左子树的值都小于二叉树的值，右子树的值都大于二叉树的值
        //先遍历左半部分，拿到左子树序列
        while(i < end && sequence[i] < sequence[end]){
            i++;
        }
        //判断右子树部分是否有小于根节点值的情况，如果有，则就不是二叉搜索树
        for(int j = i; j < end;j++){
            if(sequence[j] < sequence[end]){
                return false;
            }
        }
        return VerifySquenceOfBSTCore(sequence,start,i - 1) && VerifySquenceOfBSTCore(sequence,i,end - 1);

    }
    public boolean VerifySquenceOfBST(int [] sequence) {
        if(sequence == null || sequence.length == 0){
            return false;
        }
        return VerifySquenceOfBSTCore(sequence,0,sequence.length - 1);
    }

}
